class Solution {
public:
    string multiply(string num1, string num2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = num1.size();
        int m = num2.size();
        if (n == 0 || m == 0) { // invalid case
            return string("");
        }

        vector<int> c(n + m);
        for (int i = n - 1; i >= 0; --i) {
            int carry = 0;
            for (int j = m - 1; j >= 0 || carry; --j) {
                carry += c[n - i - 1 + m - j - 1];
                if (j >= 0) {
                    carry += static_cast<int>(num1[i] - '0') * (num2[j] - '0');
                }
                c[n - i - 1 + m - j - 1] = carry % 10;
                carry /= 10;
            }
        }

        while (c.size() > 1 && c[c.size() - 1] == 0) {
            c.pop_back();
        }
        string ans;
        for (int i = c.size() - 1; i >= 0; --i) {
            ans += static_cast<char>(c[i] + '0');
        }
        return ans;
    }
};
